1. Background and Relevant Art
Computer systems and related technology affect many aspects of society. Indeed, the computer system's ability to process information has transformed the way we live and work. Computer systems now commonly perform a host of tasks (e.g., word processing, scheduling, accounting, etc.) that prior to the advent of the computer system were performed manually. More recently, computer systems have been coupled to one another and to other electronic devices to form both wired and wireless computer networks over which the computer systems and other electronic devices can transfer electronic data. Accordingly, the performance of many computing tasks are distributed across a number of different computer systems and/or a number of different computing components.
For example, many businesses have a main office and one or more branch offices at various different geographical locations. Each office can have varying quantities and configurations of computer systems. Some businesses consolidate computing functionality at a main office and push services and applications from the main officer out to branch offices. This conserves costs since only one facility and trained personnel are needed to maintain the computing functionality.
However, this also results in more data being transferred across Wide Area Networks (“WANs”) between the main and branch offices. Many businesses that push services and applications, at least from time to time, transfer quantities of data that approach, or even exceed, the capacity of their Wide Area links. This results in depleted bandwidth and increases end-user wait times, which can make collaboration between offices difficult, if not impossible.
One aspect of retrieving data from a main office as opposed to a branch office, is that the transferred data may have been exchanged before, or includes only small modifications of previously transferred data. That is, data may be downloaded from a site, modified, and subsequently loaded back to the site. For example, a document stored on a server at main office can be opened in a word processor at a branch officer, modified, and subsequently saved from the branch office back to the main office.
Various WAN optimizations have been developed to improve use-experience between a branch and a main office, for example, in environments where similar (or exact) data is exchanged multiple times. Data compression is an example of one WAN optimization that can be used to conserver bandwidth and improve user experience. More precisely, local differential compression algorithms can utilize previously transferred data for compressing the new data.
An intermediate computer system (between a sending and receiving computer system), such as, for example, a WAN accelerator, can maintain a cache of previously transferred data. When new data for transfer is received, the intermediate computer system refers to the cache to determine if the new data is at least similar (and potentially identical) to previously transferred data. When a match is found, this indicates to the intermediate computer system that another intermediate computer system (relatively closer to receiving computer system) also has the previously transferred data cached. Thus, the intermediate computer system replaces the matching data with an offset and length into the previously transferred (cached) data. Accordingly, the intermediate computer system then transfers a combination of one or more lengths and offsets for matched data along with the bytes of any unmatched data, instead of transferring bytes for all of the new data. Transferring lengths and offsets for matching data consumes considerably less bandwidth than re-transferring the data itself
Typical local differential compression algorithms work with a relatively high level of precision by maintaining a suffix-tree of a window of scanned data. The suffix tree is used to compress the currently scanned bytes. The size of the suffix tree is queried and modified at every byte position. Thus, the suffix tree is typically cached, for example, in volatile L1 or L2 cache associated with a processor, in order to make compression work efficiently.
However, memory constraints limit the amount of time data remains compressible. For example, older data may be removed from the cache to make way for newer data even though a reasonable likelihood exists that the older data will be transferred again. Unfortunately, if the older data is transferred again, no compression is available and the bytes of older data are instead transferred, unnecessarily consuming network bandwidth.
Some scalability may be available at intermediate computer systems by adding more system memory. However, practical limitations, such as, for example, cost, system capability, etc., can still limit cache size. Thus, in some environments, (even those environments with intermediate computer systems having the maximum allowable amount of system memory) previously transferred data can still be prematurely removed from cache.